
 <!DOCTYPE HTML>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
  
    <title>经典排序算法总结与实现 | Jark&#39;s Blog</title>
    <meta name="viewport" content="width=device-width, initial-scale=1,user-scalable=no">
    
    <meta name="author" content="WuChong">
    
    <meta name="description" itemprop="description" content="经典排序算法在面试中占有很大的比重，也是基础，为了未雨绸缪，在寒假里整理并用Python实现了七大经典排序算法，包括冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序。希望能帮助到有需要的同学。之所以用Python实现，主要是因为它更接近伪代码，更利于理解。">
    
    
    <meta name="description" content="经典排序算法在面试中占有很大的比重，也是基础，为了未雨绸缪，在寒假里整理并用Python实现了七大经典排序算法，包括冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序。希望能帮助到有需要的同学。之所以用Python实现，主要是因为它更接近伪代码，更利于理解。">
<meta property="og:type" content="article">
<meta property="og:title" content="经典排序算法总结与实现">
<meta property="og:url" content="http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/">
<meta property="og:site_name" content="Jark's Blog">
<meta property="og:description" content="经典排序算法在面试中占有很大的比重，也是基础，为了未雨绸缪，在寒假里整理并用Python实现了七大经典排序算法，包括冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序。希望能帮助到有需要的同学。之所以用Python实现，主要是因为它更接近伪代码，更利于理解。">
<meta property="og:image" content="/img/Insertion-sort-example-300px.gif">
<meta property="og:image" content="/img/Merge-sort-example-300px.gif">
<meta property="og:image" content="/img/Quicksort-example.gif">
<meta property="og:image" content="/img/Heapsort-example.gif">
<meta property="og:image" content="http://ww1.sinaimg.cn/large/81b78497jw1emncvtdf1qj20u10afn0r.jpg">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="经典排序算法总结与实现">
<meta name="twitter:description" content="经典排序算法在面试中占有很大的比重，也是基础，为了未雨绸缪，在寒假里整理并用Python实现了七大经典排序算法，包括冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序。希望能帮助到有需要的同学。之所以用Python实现，主要是因为它更接近伪代码，更利于理解。">
<meta name="twitter:creator" content="@jarkwu">
<link rel="publisher" href="111190881341800841449">

    
    <link rel="alternative" href="/atom.xml" title="Jark&#39;s Blog" type="application/atom+xml">
    
    
    <link rel="icon" href="/img/favicon.ico">
    
    
    <link rel="apple-touch-icon" href="/img/jacman.jpg">
    <link rel="apple-touch-icon-precomposed" href="/img/jacman.jpg">
    
    <link rel="stylesheet" href="/css/style.css" type="text/css">
</head>

  <body>
    <header>
      <div>
		
			<div id="imglogo">
				<a href="/"><img src="/img/logo.png" alt="Jark&#39;s Blog" title="Jark&#39;s Blog"/></a>
			</div>
			
			<div id="textlogo">
				<h1 class="site-name"><a href="/" title="Jark&#39;s Blog">Jark&#39;s Blog</a></h1>
				<h2 class="blog-motto">当你的才华还撑不起你的野心时，你就应该静下心来学习。</h2>
			</div>
			<div class="navbar"><a class="navbutton navmobile" href="#" title="菜单">
			</a></div>
			<nav class="animated">
				<ul>
					<ul>
					 
						<li><a href="/">首页</a></li>
					
						<li><a href="/archives">归档</a></li>
					
						<li><a href="/about">关于</a></li>
					
					<li>
 					
						<form class="search" action="http://zhannei.baidu.com/cse/search" target="_blank">
							<label>Search</label>
						<input name="s" type="hidden" value= 783281470518440642 ><input type="text" name="q" size="30" placeholder="搜索"><br>
						</form>
					
					</li>
				</ul>
			</nav>			
</div>
    </header>
    <div id="container">
      <div id="main" class="post" itemscope itemprop="blogPost">
  
	<article itemprop="articleBody"> 
		<header class="article-info clearfix">
  <h1 itemprop="name">
    
      <a href="/blog/2014/02/09/algorithm-sort-summary/" title="经典排序算法总结与实现" itemprop="url">经典排序算法总结与实现</a>
  </h1>
  <p class="article-author">By
       
		<a href="https://plus.google.com/111190881341800841449?rel=author" title="WuChong" target="_blank" itemprop="author">WuChong</a>
		
  <p class="article-time">
    <time datetime="2014-02-09T15:48:26.000Z" itemprop="datePublished"> 发表于 2014-02-09</time>
    
  </p>
</header>
	<div class="article-content">
		
		<div id="toc" class="toc-article">
			<strong class="toc-title">文章目录</strong>
		
		<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#一、冒泡排序_BubbleSort"><span class="toc-text">一、冒泡排序 BubbleSort</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#三、插入排序_InsertionSort"><span class="toc-text">三、插入排序 InsertionSort</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#四、希尔排序_ShellSort"><span class="toc-text">四、希尔排序 ShellSort</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#五、归并排序_MergeSort"><span class="toc-text">五、归并排序 MergeSort</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#六、快速排序_QuickSort"><span class="toc-text">六、快速排序 QuickSort</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#七、堆排序_HeapSort"><span class="toc-text">七、堆排序 HeapSort</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#总结"><span class="toc-text">总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#参考资料"><span class="toc-text">参考资料</span></a></li></ol>
		
		</div>
		
		<p>经典排序算法在面试中占有很大的比重，也是基础，为了未雨绸缪，在寒假里整理并用Python实现了七大经典排序算法，包括冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序。希望能帮助到有需要的同学。之所以用Python实现，主要是因为它更接近伪代码，能用更少的代码实现算法，更利于理解。</p>
<p>本篇博客所有排序实现均默认从小到大。</p>
<h2 id="一、冒泡排序_BubbleSort">一、冒泡排序 BubbleSort</h2>
<p><strong>介绍：</strong></p>
<p>冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。  </p>
<p><strong>步骤：</strong></p>
<ol>
<li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>
<li>对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。</li>
<li>针对所有的元素重复以上的步骤，除了最后一个。</li>
<li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>
</ol>
<p><strong>源代码：</strong>(python实现)</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
</pre></td><td class="code"><pre><span class="function"><span class="keyword">def</span> <span class="title">bubble_sort</span><span class="params">(arry)</span>:</span>
    n = len(arry)                   <span class="comment">#获得数组的长度</span>
    <span class="keyword">for</span> i <span class="keyword">in</span> range(n):
        <span class="keyword">for</span> j <span class="keyword">in</span> range(<span class="number">1</span>,n-i):
            <span class="keyword">if</span>  arry[j-<span class="number">1</span>] &gt; arry[j] :       <span class="comment">#如果前者比后者大</span>
                arry[j-<span class="number">1</span>],arry[j] = arry[j],arry[j-<span class="number">1</span>]      <span class="comment">#则交换两者</span>
    <span class="keyword">return</span> arry
</pre></td></tr></table></figure><br><a id="more"></a><br><br>不过针对上述代码还有两种优化方案。<br><br>优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。<br>优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。<br><br>这两种优化方案的实现可以详见<a href="https://github.com/wuchong/Algorithm-Interview/blob/master/Sort/python/BubbleSort.py" target="_blank" rel="external">这里</a>。<br><br>##二、选择排序 SelectionSort<br><br><br><strong>介绍：</strong><br><br>选择排序无疑是最简单直观的排序。它的工作原理如下。<br><br><strong>步骤：</strong><br><br>1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。<br>2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。<br>3. 以此类推，直到所有元素均排序完毕。<br><br><strong>源代码：</strong>(python实现)<br><figure class="highlight python"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
</pre></td><td class="code"><pre><span class="function"><span class="keyword">def</span> <span class="title">select_sort</span><span class="params">(ary)</span>:</span>
    n = len(ary)
    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">0</span>,n):
        min = i                             <span class="comment">#最小元素下标标记</span>
        <span class="keyword">for</span> j <span class="keyword">in</span> range(i+<span class="number">1</span>,n):
            <span class="keyword">if</span> ary[j] &lt; ary[min] :
                min = j                     <span class="comment">#找到最小值的下标</span>
        ary[min],ary[i] = ary[i],ary[min]   <span class="comment">#交换两者</span>
    <span class="keyword">return</span> ary
</pre></td></tr></table></figure>

<h2 id="三、插入排序_InsertionSort">三、插入排序 InsertionSort</h2>
<p><strong>介绍：</strong></p>
<p>插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。</p>
<p><strong>步骤：</strong>  </p>
<ol>
<li>从第一个元素开始，该元素可以认为已经被排序</li>
<li>取出下一个元素，在已经排序的元素序列中从后向前扫描</li>
<li>如果被扫描的元素（已排序）大于新元素，将该元素后移一位</li>
<li>重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</li>
<li>将新元素插入到该位置后</li>
<li>重复步骤2~5</li>
</ol>
<p><strong>排序演示：</strong></p>
<p><img src="/img/Insertion-sort-example-300px.gif" alt=""></p>
<p><strong>源代码：</strong>(python实现)</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
</pre></td><td class="code"><pre><span class="function"><span class="keyword">def</span> <span class="title">insert_sort</span><span class="params">(ary)</span>:</span>
    n = len(ary)
    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>,n):
        <span class="keyword">if</span> ary[i] &lt; ary[i-<span class="number">1</span>]:
            temp = ary[i]
            index = i           <span class="comment">#待插入的下标</span>
            <span class="keyword">for</span> j <span class="keyword">in</span> range(i-<span class="number">1</span>,-<span class="number">1</span>,-<span class="number">1</span>):  <span class="comment">#从i-1 循环到 0 (包括0)</span>
                <span class="keyword">if</span> ary[j] &gt; temp :
                    ary[j+<span class="number">1</span>] = ary[j]
                    index = j   <span class="comment">#记录待插入下标</span>
                <span class="keyword">else</span> :
                    <span class="keyword">break</span>
            ary[index] = temp
    <span class="keyword">return</span> ary
</pre></td></tr></table></figure>

<h2 id="四、希尔排序_ShellSort">四、希尔排序 ShellSort</h2>
<p><strong>介绍：</strong></p>
<p>希尔排序，也称递减增量排序算法，实质是分组插入排序。由 Donald Shell 于1959年提出。希尔排序是非稳定排序算法。</p>
<p>希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。</p>
<p>例如，假设有这样一组数<code>[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]</code>，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：</p>
<pre><code>13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
</code></pre><p>然后我们对每列进行排序：</p>
<pre><code>10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
</code></pre><p>将上述四行数字，依序接在一起时我们得到：<code>[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]</code>。这时10已经移至正确位置了，然后再以3为步长进行排序：</p>
<pre><code>10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
</code></pre><p>排序之后变为：</p>
<pre><code>10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
</code></pre><p>最后以1步长进行排序（此时就是简单的插入排序了）。</p>
<p><strong>源代码：</strong>(python实现)</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
</pre></td><td class="code"><pre><span class="function"><span class="keyword">def</span> <span class="title">shell_sort</span><span class="params">(ary)</span>:</span>
    n = len(ary)
    gap = round(n/<span class="number">2</span>)       <span class="comment">#初始步长 , 用round四舍五入取整</span>
    <span class="keyword">while</span> gap &gt; <span class="number">0</span> :
        <span class="keyword">for</span> i <span class="keyword">in</span> range(gap,n):        <span class="comment">#每一列进行插入排序 , 从gap 到 n-1</span>
            temp = ary[i]
            j = i
            <span class="keyword">while</span> ( j &gt;= gap <span class="keyword">and</span> ary[j-gap] &gt; temp ):    <span class="comment">#插入排序</span>
                ary[j] = ary[j-gap]
                j = j - gap
            ary[j] = temp
        gap = round(gap/<span class="number">2</span>)                     <span class="comment">#重新设置步长</span>
    <span class="keyword">return</span> ary
</pre></td></tr></table></figure>

<p>上面源码的步长的选择是从<code>n/2</code>开始，每次再减半，直至为0。步长的选择直接决定了希尔排序的复杂度。在<a href="http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F#.E6.AD.A5.E9.95.BF.E5.BA.8F.E5.88.97" target="_blank" rel="external">维基百科</a>上有对于步长串行的详细介绍。</p>
<h2 id="五、归并排序_MergeSort">五、归并排序 MergeSort</h2>
<p><strong>介绍：</strong></p>
<p>归并排序是采用分治法的一个非常典型的应用。<code>归并</code>排序的思想就是先递<code>归</code>分解数组，再<code>合</code>并数组。</p>
<p>先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。</p>
<p>再考虑递归分解，基本思路是将数组分解成<code>left</code>和<code>right</code>，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。</p>
<p><strong>排序演示：</strong></p>
<p><img src="/img/Merge-sort-example-300px.gif" alt=""></p>
<p><strong>源代码：</strong>(python实现)</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
</pre></td><td class="code"><pre><span class="function"><span class="keyword">def</span> <span class="title">merge_sort</span><span class="params">(ary)</span>:</span>
    <span class="keyword">if</span> len(ary) &lt;= <span class="number">1</span> : <span class="keyword">return</span> ary
    num = int(len(ary)/<span class="number">2</span>)       <span class="comment">#二分分解</span>
    left = merge_sort(ary[:num])
    right = merge_sort(ary[num:])
    <span class="keyword">return</span> merge(left,right)    <span class="comment">#合并数组</span>

<span class="function"><span class="keyword">def</span> <span class="title">merge</span><span class="params">(left,right)</span>:</span>
    <span class="string">'''合并操作，
    将两个有序数组left[]和right[]合并成一个大的有序数组'''</span>
    l,r = <span class="number">0</span>,<span class="number">0</span>           <span class="comment">#left与right数组的下标指针</span>
    result = []
    <span class="keyword">while</span> l&lt;len(left) <span class="keyword">and</span> r&lt;len(right) :
        <span class="keyword">if</span> left[l] &lt; right[r]:
            result.append(left[l])
            l += <span class="number">1</span>
        <span class="keyword">else</span>:
            result.append(right[r])
            r += <span class="number">1</span>
    result += left[l:]
    result += right[r:]
    <span class="keyword">return</span> result
</pre></td></tr></table></figure>

<h2 id="六、快速排序_QuickSort">六、快速排序 QuickSort</h2>
<p><strong>介绍：</strong><br>快速排序通常明显比同为<em>Ο(n log n)</em>的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。</p>
<p><strong>步骤：</strong>  </p>
<ol>
<li>从数列中挑出一个元素作为基准数。</li>
<li>分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。</li>
<li>再对左右区间递归执行第二步，直至各区间只有一个数。</li>
</ol>
<p><strong>排序演示：</strong></p>
<p><img src="/img/Quicksort-example.gif" alt=""></p>
<p><strong>源代码：</strong>(python实现)</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
</pre></td><td class="code"><pre><span class="function"><span class="keyword">def</span> <span class="title">quick_sort</span><span class="params">(ary)</span>:</span>
    <span class="keyword">return</span> qsort(ary,<span class="number">0</span>,len(ary)-<span class="number">1</span>)

<span class="function"><span class="keyword">def</span> <span class="title">qsort</span><span class="params">(ary,left,right)</span>:</span>
    <span class="comment">#快排函数，ary为待排序数组，left为待排序的左边界，right为右边界</span>
    <span class="keyword">if</span> left &gt;= right : <span class="keyword">return</span> ary
    key = ary[left]     <span class="comment">#取最左边的为基准数</span>
    lp = left           <span class="comment">#左指针</span>
    rp = right          <span class="comment">#右指针</span>
    <span class="keyword">while</span> lp &lt; rp :
        <span class="keyword">while</span> ary[rp] &gt;= key <span class="keyword">and</span> lp &lt; rp :
            rp -= <span class="number">1</span>
        <span class="keyword">while</span> ary[lp] &lt;= key <span class="keyword">and</span> lp &lt; rp :
            lp += <span class="number">1</span>
        ary[lp],ary[rp] = ary[rp],ary[lp]
    ary[left],ary[lp] = ary[lp],ary[left]
    qsort(ary,left,lp-<span class="number">1</span>)
    qsort(ary,rp+<span class="number">1</span>,right)
    <span class="keyword">return</span> ary
</pre></td></tr></table></figure>

<h2 id="七、堆排序_HeapSort">七、堆排序 HeapSort</h2>
<p><strong>介绍：</strong></p>
<p>堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。</p>
<p><strong>二叉堆具有以下性质：</strong>  </p>
<ol>
<li>父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。  </li>
<li>每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。  </li>
</ol>
<p><strong>步骤：</strong></p>
<ol>
<li><p>构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标<code>n/2</code>开始的元素均为大根堆。于是只要从<code>n/2-1</code>开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。</p>
</li>
<li><p>堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将<code>heap[0]</code>与<code>heap[n-1]</code>交换，再对<code>heap[0...n-2]</code>做最大堆调整。第二次将<code>heap[0]</code>与<code>heap[n-2]</code>交换，再对<code>heap[0...n-3]</code>做最大堆调整。重复该操作直至<code>heap[0]</code>和<code>heap[1]</code>交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。</p>
</li>
<li><p>最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。</p>
</li>
</ol>
<p><strong>排序演示：</strong></p>
<p><img src="/img/Heapsort-example.gif" alt=""></p>
<p><strong>源代码：</strong>(python实现)</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
</pre></td><td class="code"><pre><span class="function"><span class="keyword">def</span> <span class="title">heap_sort</span><span class="params">(ary)</span> :</span>
    n = len(ary)
    first = int(n/<span class="number">2</span>-<span class="number">1</span>)       <span class="comment">#最后一个非叶子节点</span>
    <span class="keyword">for</span> start <span class="keyword">in</span> range(first,-<span class="number">1</span>,-<span class="number">1</span>) :     <span class="comment">#构造大根堆</span>
        max_heapify(ary,start,n-<span class="number">1</span>)
    <span class="keyword">for</span> end <span class="keyword">in</span> range(n-<span class="number">1</span>,<span class="number">0</span>,-<span class="number">1</span>):           <span class="comment">#堆排，将大根堆转换成有序数组</span>
        ary[end],ary[<span class="number">0</span>] = ary[<span class="number">0</span>],ary[end]
        max_heapify(ary,<span class="number">0</span>,end-<span class="number">1</span>)
    <span class="keyword">return</span> ary


<span class="comment">#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点</span>
<span class="comment">#start为当前需要调整最大堆的位置，end为调整边界</span>
<span class="function"><span class="keyword">def</span> <span class="title">max_heapify</span><span class="params">(ary,start,end)</span>:</span>
    root = start
    <span class="keyword">while</span> <span class="keyword">True</span> :
        child = root*<span class="number">2</span> +<span class="number">1</span>               <span class="comment">#调整节点的子节点</span>
        <span class="keyword">if</span> child &gt; end : <span class="keyword">break</span>
        <span class="keyword">if</span> child+<span class="number">1</span> &lt;= end <span class="keyword">and</span> ary[child] &lt; ary[child+<span class="number">1</span>] :
            child = child+<span class="number">1</span>             <span class="comment">#取较大的子节点</span>
        <span class="keyword">if</span> ary[root] &lt; ary[child] :     <span class="comment">#较大的子节点成为父节点</span>
            ary[root],ary[child] = ary[child],ary[root]     <span class="comment">#交换</span>
            root = child
        <span class="keyword">else</span> :
            <span class="keyword">break</span>
</pre></td></tr></table></figure>

<h2 id="总结">总结</h2>
<p>下面为七种经典排序算法指标对比情况：</p>
<p><img src="http://ww1.sinaimg.cn/large/81b78497jw1emncvtdf1qj20u10afn0r.jpg" alt=""></p>
<h2 id="参考资料">参考资料</h2>
<ul>
<li>维基百科：<a href="http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F" target="_blank" rel="external">希尔排序</a>，<a href="http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F" target="_blank" rel="external">快速排序</a>，<a href="http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F" target="_blank" rel="external">归并排序</a>，<a href="http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F" target="_blank" rel="external">堆排序</a></li>
<li><a href="http://blog.csdn.net/morewindows/article/details/7961256" target="_blank" rel="external">白话经典算法系列</a></li>
<li><a href="http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html" target="_blank" rel="external">排序算法可视化</a></li>
<li><a href="http://blog.csdn.net/super_chris/article/details/4581900" target="_blank" rel="external">所谓堆和堆排序</a></li>
<li><a href="http://6924918.blog.51cto.com/6914918/1260860" target="_blank" rel="external">几种经典排序算法</a></li>
</ul>
<p>注：本文所有源代码已共享到<a href="https://github.com/wuchong/Algorithm-Interview/tree/master/Sort/python" target="_blank" rel="external">GitHub</a>。 </p>
<p>-EOF-</p>
  
	</div>
		<footer class="article-footer clearfix">
<div class="article-catetags">

<div class="article-categories">
  <span></span>
  <a class="article-category-link" href="/categories/程序设计/">程序设计</a>
</div>


  <div class="article-tags">
  
  <span></span> <a href="/tags/算法/">算法</a><a href="/tags/Python/">Python</a><a href="/tags/面试/">面试</a>
  </div>

</div>



	<div class="article-share" id="share">
	
	  <div data-url="http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/" data-title="经典排序算法总结与实现 | Jark&#39;s Blog" data-tsina="2176287895" class="share clearfix">
	  </div>
	
	</div>


</footer>

   	       
	</article>
	
<nav class="article-nav clearfix">
 
 <div class="prev" >
 <a href="/blog/2014/02/25/jquery-datatable-sort-plugin/" title="jQuery.dataTables 自定义排序">
  <strong>上一篇：</strong><br/>
  <span>
  jQuery.dataTables 自定义排序</span>
</a>
</div>


<div class="next">
<a href="/blog/2014/01/27/python-spider-gif/"  title="Python爬虫：暴走漫画上的GIF趣图">
 <strong>下一篇：</strong><br/> 
 <span>Python爬虫：暴走漫画上的GIF趣图
</span>
</a>
</div>

</nav>

	
<section id="comments" class="comment">
	<div class="ds-thread" data-thread-key="blog/2014/02/09/algorithm-sort-summary/" data-title="经典排序算法总结与实现" data-url="http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/"></div>
</section>


</div>  
      <div class="openaside"><a class="navbutton" href="#" title="显示侧边栏"></a></div>

<div id="asidepart">
<div class="closeaside"><a class="closebutton" href="#" title="隐藏侧边栏"></a></div>
<aside class="clearfix">

  
<div class="categorieslist">
	<p class="asidetitle">分类</p>
		<ul>
		
			<li><a href="/categories/Hexo/" title="Hexo">Hexo<sup>7</sup></a></li>
		
			<li><a href="/categories/LinuxUnix/" title="Linux/Unix">Linux/Unix<sup>6</sup></a></li>
		
			<li><a href="/categories/Python/" title="Python">Python<sup>3</sup></a></li>
		
			<li><a href="/categories/推荐系统/" title="推荐系统">推荐系统<sup>3</sup></a></li>
		
			<li><a href="/categories/杂项资源/" title="杂项资源">杂项资源<sup>2</sup></a></li>
		
			<li><a href="/categories/程序设计/" title="程序设计">程序设计<sup>5</sup></a></li>
		
			<li><a href="/categories/系统架构/" title="系统架构">系统架构<sup>1</sup></a></li>
		
			<li><a href="/categories/编程语言/" title="编程语言">编程语言<sup>2</sup></a></li>
		
			<li><a href="/categories/职场生涯/" title="职场生涯">职场生涯<sup>2</sup></a></li>
		
			<li><a href="/categories/随笔生活/" title="随笔生活">随笔生活<sup>5</sup></a></li>
		
		</ul>
</div>


  
<div class="tagslist">
	<p class="asidetitle">标签</p>
		<ul class="clearfix">
		
			<li><a href="/tags/Hexo/" title="Hexo">Hexo<sup>8</sup></a></li>
		
			<li><a href="/tags/面试/" title="面试">面试<sup>5</sup></a></li>
		
			<li><a href="/tags/Linux基础/" title="Linux基础">Linux基础<sup>5</sup></a></li>
		
			<li><a href="/tags/生活/" title="生活">生活<sup>4</sup></a></li>
		
			<li><a href="/tags/博客/" title="博客">博客<sup>4</sup></a></li>
		
			<li><a href="/tags/Python/" title="Python">Python<sup>4</sup></a></li>
		
			<li><a href="/tags/阿里推荐大赛/" title="阿里推荐大赛">阿里推荐大赛<sup>4</sup></a></li>
		
			<li><a href="/tags/算法/" title="算法">算法<sup>2</sup></a></li>
		
			<li><a href="/tags/爬虫/" title="爬虫">爬虫<sup>2</sup></a></li>
		
			<li><a href="/tags/ODPS/" title="ODPS">ODPS<sup>2</sup></a></li>
		
			<li><a href="/tags/教程/" title="教程">教程<sup>2</sup></a></li>
		
			<li><a href="/tags/Jacman/" title="Jacman">Jacman<sup>2</sup></a></li>
		
			<li><a href="/tags/Java/" title="Java">Java<sup>2</sup></a></li>
		
			<li><a href="/tags/文件系统/" title="文件系统">文件系统<sup>2</sup></a></li>
		
			<li><a href="/tags/启动流程/" title="启动流程">启动流程<sup>1</sup></a></li>
		
			<li><a href="/tags/权限/" title="权限">权限<sup>1</sup></a></li>
		
			<li><a href="/tags/正则表达式/" title="正则表达式">正则表达式<sup>1</sup></a></li>
		
			<li><a href="/tags/jQuery/" title="jQuery">jQuery<sup>1</sup></a></li>
		
			<li><a href="/tags/双检锁/" title="双检锁">双检锁<sup>1</sup></a></li>
		
			<li><a href="/tags/设计模式/" title="设计模式">设计模式<sup>1</sup></a></li>
		
		</ul>
</div>


  <div class="linkslist">
  <p class="asidetitle">友情链接</p>
    <ul>
        
          <li>
            <a href="https://coderq.com" target="_blank" title="码农圈">码农圈</a>
          </li>
        
          <li>
            <a href="http://zipperary.com/" target="_blank" title="Zippera&#39;s Blog">Zippera&#39;s Blog</a>
          </li>
        
          <li>
            <a href="http://hijiangtao.github.io/" target="_blank" title="Data.Blog">Data.Blog</a>
          </li>
        
    </ul>
</div>

  <div class="weiboshow">
  <p class="asidetitle">新浪微博</p>
    <iframe width="100%" height="119" class="share_self"  frameborder="0" scrolling="no" src="http://widget.weibo.com/weiboshow/index.php?language=&width=0&height=119&fansRow=2&ptype=1&speed=0&skin=9&isTitle=1&noborder=1&isWeibo=0&isFans=0&uid=2176287895&verifier=b3593ceb&dpc=1"></iframe>
</div>


  <div class="rsspart">
	<a href="/atom.xml" target="_blank" title="rss">RSS 订阅</a>
</div>

</aside>
</div>
    </div>
    <footer><div id="footer" >
	
	<div class="line">
		<span></span>
		<div class="author"></div>
	</div>
	
	
	<section class="info">
		<p> Hello,I&#39;m WuChong. For now I&#39;m a graduate student in Beijing. <br/>
			I&#39;ll share my learning experience with you at this blog.</p>
	</section>
	 
	<div class="social-font" class="clearfix">
		
		<a href="http://weibo.com/wuchong1014" target="_blank" class="icon-weibo" title="微博"></a>
		
		
		<a href="https://github.com/wuchong" target="_blank" class="icon-github" title="github"></a>
		
		
		
		<a href="https://twitter.com/jarkwu" target="_blank" class="icon-twitter" title="twitter"></a>
		
		
		
		
		
		
		<a href="https://plus.google.com/111190881341800841449?rel=author" target="_blank" class="icon-google_plus" title="Google+"></a>
		
		
	</div>
		<p class="copyright">Powered by <a href="http://zespia.tw/hexo/" target="_blank" title="hexo">hexo</a> and Theme by <a href="https://github.com/wuchong/jacman" target="_blank" title="Pacman">Jacman</a> © 2014 
		
		<a href="http://wuchong.me/about" target="_blank" title="WuChong">WuChong</a>
		
		</p>
</div>
</footer>
    <script src="/js/jquery-2.0.3.min.js"></script>
<script src="/js/jquery.imagesloaded.min.js"></script>
<script src="/js/gallery.js"></script>

<script type="text/javascript">
$(document).ready(function(){ 
  $('.navbar').click(function(){
    $('header nav').toggleClass('shownav');
  });
  var myWidth = 0;
  function getSize(){
    if( typeof( window.innerWidth ) == 'number' ) {
      myWidth = window.innerWidth;
    } else if( document.documentElement && document.documentElement.clientWidth) {
      myWidth = document.documentElement.clientWidth;
    };
  };
  var m = $('#main'),
      a = $('#asidepart'),
      c = $('.closeaside'),
      o = $('.openaside');
  $(window).resize(function(){
    getSize(); 
    if (myWidth >= 1024) {
      $('header nav').removeClass('shownav');
    }else
    {
      m.removeClass('moveMain');
      a.css('display', 'block').removeClass('fadeOut');
      o.css('display', 'none');
        
    }
  });
  c.click(function(){
    a.addClass('fadeOut').css('display', 'none');
    o.css('display', 'block').addClass('fadeIn');
    m.addClass('moveMain');
  });
  o.click(function(){
    o.css('display', 'none').removeClass('beforeFadeIn');
    a.css('display', 'block').removeClass('fadeOut').addClass('fadeIn');      
    m.removeClass('moveMain');
  });
  $(window).scroll(function(){
    o.css("top",Math.max(80,260-$(this).scrollTop()));
  });
});
</script>

<script type="text/javascript">
$(document).ready(function(){ 
  var ai = $('.article-content>iframe'),
      ae = $('.article-content>embed'),
      t  = $('#toc'),
      h  = $('article h2')
      ah = $('article h2'),
      ta = $('#toc.toc-aside'),
      o  = $('.openaside'),
      c  = $('.closeaside');
  if(ai.length>0){
    ai.wrap('<div class="video-container" />');
  };
  if(ae.length>0){
   ae.wrap('<div class="video-container" />');
  };
  if(ah.length==0){
    t.css('display','none');
  }else{
    c.click(function(){
      ta.css('display', 'block').addClass('fadeIn');
    });
    o.click(function(){
      ta.css('display', 'none');
    });
    $(window).scroll(function(){
      ta.css("top",Math.max(140,320-$(this).scrollTop()));
    });
  };
});
</script>


<script type="text/javascript">
$(document).ready(function(){ 
  var $this = $('.share'),
      url = $this.attr('data-url'),
      encodedUrl = encodeURIComponent(url),
      title = $this.attr('data-title'),
      tsina = $this.attr('data-tsina'),
      description = $this.attr('description');
  var html = [
  '<a href="#" class="overlay" id="qrcode"></a>',
  '<div class="qrcode clearfix"><span>扫描二维码分享到微信朋友圈</span><a class="qrclose" href="#nothing"></a><strong>Loading...Please wait</strong><img id="qrcode-pic" data-src="http://s.jiathis.com/qrcode.php?url=' + encodedUrl + '"/></div>',
  '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="article-share-facebook" target="_blank" title="Facebook"></a>',
  '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="article-share-twitter" target="_blank" title="Twitter"></a>',
  '<a href="#qrcode" class="article-share-qrcode" title="微信"></a>',
  '<a href="http://widget.renren.com/dialog/share?resourceUrl=' + encodedUrl + '&srcUrl=' + encodedUrl + '&title=' + title +'" class="article-share-renren" target="_blank" title="人人"></a>',
  '<a href="http://service.weibo.com/share/share.php?title='+title+'&url='+encodedUrl +'&ralateUid='+ tsina +'&searchPic=true&style=number' +'" class="article-share-weibo" target="_blank" title="微博"></a>',
  '<span title="Share to"></span>'
  ].join('');
  $this.append(html);
  $('.article-share-qrcode').click(function(){
    var imgSrc = $('#qrcode-pic').attr('data-src');
    $('#qrcode-pic').attr('src', imgSrc);
    $('#qrcode-pic').load(function(){
        $('.qrcode strong').text(' ');
    });
  });
});     
</script>



<script type="text/javascript">
  var duoshuoQuery = {short_name:"wuchong"};
  (function() {
    var ds = document.createElement('script');
    ds.type = 'text/javascript';ds.async = true;
    ds.src = '//static.duoshuo.com/embed.js';
    ds.charset = 'UTF-8';
    (document.getElementsByTagName('head')[0] 
    || document.getElementsByTagName('body')[0]).appendChild(ds);
  })();
</script> 







<link rel="stylesheet" href="/fancybox/jquery.fancybox.css" media="screen" type="text/css">
<script src="/fancybox/jquery.fancybox.pack.js"></script>
<script type="text/javascript">
$(document).ready(function(){ 
  $('.article-content').each(function(i){
    $(this).find('img').each(function(){
      if ($(this).parent().hasClass('fancybox')) return;
      var alt = this.alt;
      if (alt) $(this).after('<span class="caption">' + alt + '</span>');
      $(this).wrap('<a href="' + this.src + '" title="' + alt + '" class="fancybox"></a>');
    });
    $(this).find('.fancybox').each(function(){
      $(this).attr('rel', 'article' + i);
    });
  });
  if($.fancybox){
    $('.fancybox').fancybox();
  }
}); 
</script>



<!-- Analytics Begin -->

<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46321946-2', 'wuchong.me');  
ga('send', 'pageview');
</script>





<!-- Analytics End -->

<!-- Totop Begin -->

	<div id="totop">
	<a title="返回顶部"><img src="/img/scrollup.png"/></a>
	</div>
	<script src="/js/totop.js"></script>

<!-- Totop End -->

<!-- MathJax Begin -->
<!-- mathjax config similar to math.stackexchange -->


<!-- MathJax End -->

  </body>
</html>
